package h0814;

import java.util.*;
/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 文件缓存系统
 * @date 2024/8/14 17:09
 */

public class FileCacheSystem {
    private int maxSize;
    private int currentSize;
    private int currentTime;
    private Map<String, FileInfo> cache;
    private PriorityQueue<FileInfo> fileQueue;

    public FileCacheSystem(int maxSize) {
        this.maxSize = maxSize;
        this.currentSize = 0;
        this.currentTime = 0;
        this.cache = new HashMap<>();
        this.fileQueue = new PriorityQueue<>((a, b) -> {
            if (a.accessCount != b.accessCount) {
                return Integer.compare(a.accessCount, b.accessCount);
            } else {
                return Integer.compare(a.lastAccessTime, b.lastAccessTime);
            }
        });
    }

    public void put(String fileName, int fileSize) {
        if (cache.containsKey(fileName) || fileSize > maxSize) {
            return;
        }

        while (currentSize + fileSize > maxSize) {
            FileInfo fileToRemove = fileQueue.poll();
            if (fileToRemove != null) {
                cache.remove(fileToRemove.fileName);
                currentSize -= fileToRemove.fileSize;
            }
        }

        currentTime++;
        FileInfo newFile = new FileInfo(fileName, fileSize, 0, currentTime);
        cache.put(fileName, newFile);
        fileQueue.add(newFile);
        currentSize += fileSize;
    }

    public void get(String fileName) {
        FileInfo fileInfo = cache.get(fileName);
        if (fileInfo != null) {
            fileQueue.remove(fileInfo);
            currentTime++;
            fileInfo.accessCount++;
            fileInfo.lastAccessTime = currentTime;
            fileQueue.add(fileInfo);
        }
    }

    public void printCache() {
        List<String> fileNames = new ArrayList<>(cache.keySet());
        if (fileNames.isEmpty()) {
            System.out.println("NONE");
        } else {
            Collections.sort(fileNames);
            System.out.println(String.join(",", fileNames));
        }
    }

    private static class FileInfo {
        String fileName;
        int fileSize;
        int accessCount;
        int lastAccessTime;

        public FileInfo(String fileName, int fileSize, int accessCount, int lastAccessTime) {
            this.fileName = fileName;
            this.fileSize = fileSize;
            this.accessCount = accessCount;
            this.lastAccessTime = lastAccessTime;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int maxSize = scanner.nextInt();
        int n = scanner.nextInt();
        scanner.nextLine();

        FileCacheSystem fileCacheSystem = new FileCacheSystem(maxSize);

        for (int i = 0; i < n; i++) {
            String[] parts = scanner.nextLine().split(" ");
            String op = parts[0];
            String fileName = parts[1];
            if (op.equals("put")) {
                int fileSize = Integer.parseInt(parts[2]);
                fileCacheSystem.put(fileName, fileSize);
            } else if (op.equals("get")) {
                fileCacheSystem.get(fileName);
            }
        }

        fileCacheSystem.printCache();
    }
}
